package algo.LocalSearch;


import java.util.HashSet;
import algo.Model.*;

import java.util.Queue;
import java.util.LinkedList;
import java.util.Iterator;

import java.util.HashMap;
import java.util.Vector;

public class LocalSolver {
	BasicLocalSearchEntity[]	_o;	
	//HashSet<BasicLocalSearchEntity>[] 	_adj;// _adj[o.getID()] is the set of entities that depend on o
	
	//tmp variables
	//HashSet<BasicLocalSearchEntity>	_to;
	Vector<BasicLocalSearchEntity>	_to;
	HashMap<BasicLocalSearchEntity, HashSet<BasicLocalSearchEntity>> 		_map;// _map[o] is the set of entities that o defines
	HashMap<BasicLocalSearchEntity, HashSet<BasicLocalSearchEntity>> 		_mapDependency;// _mapDependency[o] is the set of entities on which o depends
	
	
	public LocalSolver(){
		//_to = new HashSet<BasicLocalSearchEntity>();
		_to = new Vector<BasicLocalSearchEntity>();
		_map = new HashMap<BasicLocalSearchEntity, HashSet<BasicLocalSearchEntity>>();
		_mapDependency = new HashMap<BasicLocalSearchEntity, HashSet<BasicLocalSearchEntity>>();
	}
	
	void post(BasicLocalSearchEntity e){
		//System.out.println("LocalSearch::post entity " + e.name());
		_to.add(e);
		
		/* construct the dependency graph in the close method
		if(_map.get(e) == null)
			_map.put(e, new HashSet<BasicLocalSearchEntity>());
		if(_mapDependency.get(e) == null)
			_mapDependency.put(e, new HashSet<BasicLocalSearchEntity>());
		BasicLocalSearchEntity[] de = e.getDependEntities();
		if(de != null){
			for(int i = 0; i < de.length; i++){
				//HashSet<BasicLocalSearchEntity> S = _map.get(de[i]);
				//S.add(e);
				_map.get(de[i]).add(e);
				_mapDependency.get(e).add(de[i]);
			}			
		}
		*/
	}
	
	void propagateInt(VarInt x, int val){
		
		//System.out.println("LocalSolver::propagateInt(" + x.name() + "," + val + ")");
		
		//x.setValue(val);
		Queue Q = new LinkedList<BasicLocalSearchEntity>();
		//Q.add(x);
		//int idx = (int)x.getID();
		//Iterator it = _adj[idx].iterator();
		HashSet<BasicLocalSearchEntity> A = _map.get(x);
		Iterator it = A.iterator();
		while(it.hasNext()){
			BasicLocalSearchEntity e = (BasicLocalSearchEntity)it.next();
			Q.add(e);
			//System.out.println("LocalSolver::propagateInt(" + x.name() + "," + val + ") -> Q.enqueue(" + e.name() + ")");
		}
		//return;
		
		while(!Q.isEmpty()){
			//IFunction f = (IFunction)Q.poll();
			BasicLocalSearchEntity f = (BasicLocalSearchEntity)Q.poll();
			//System.out.println("LocalSolver::propagateInt(" + x.name() + "," + val + ") -> Q.dequeue(" + f.name() + ")");
			f.propagateInt(x, val);
			BasicLocalSearchEntity o = (BasicLocalSearchEntity)f;
			HashSet<BasicLocalSearchEntity> Aj = _map.get(o);
			Iterator j = Aj.iterator();//_adj[(int)f.getID()].iterator();
			while(j.hasNext()){
				BasicLocalSearchEntity e = (BasicLocalSearchEntity)j.next();
				if(!Q.contains(e)){
					Q.add(e);
					//System.out.println("LocalSolver::propagateInt(" + x.name() + "," + val + ") -> LOOP Q.enqueue(" + e.name() + ")");
				}
			}
			//break;
		}
		
	}
	void initPropagate(){
		Queue Q = new LinkedList<BasicLocalSearchEntity>();
		for(int i = 0; i < _o.length; i++){
			if(_mapDependency.get(_o[i]).size() == 0){// initially enqueue only variables which do not depend on any entities
				HashSet<BasicLocalSearchEntity> A = _map.get(_o[i]);
				Iterator it = A.iterator();//_adj[(int)_o[i].getID()].iterator();
				while(it.hasNext()){
					BasicLocalSearchEntity e = (BasicLocalSearchEntity)it.next();
					if(!Q.contains(e)){
						Q.add(e);
						//System.out.println("LocalSearch::initPropagate, Q->push(" + e.name() + ")");
					}
				}
			}
		}
		while(!Q.isEmpty()){
			//IFunction f = (IFunction)Q.poll();
			BasicLocalSearchEntity f = (BasicLocalSearchEntity)Q.poll();
			//System.out.println("LocalSearch::initPropagate, Q->pop(" + f.name() + ")");
			f.initPropagate();
			BasicLocalSearchEntity o = (BasicLocalSearchEntity)f;
			HashSet<BasicLocalSearchEntity> A = _map.get(o);
			Iterator it = A.iterator();//_adj[(int)_o[i].getID()].iterator();
			while(it.hasNext()){
				BasicLocalSearchEntity e = (BasicLocalSearchEntity)it.next();
				if(!Q.contains(e))
					Q.add(e);
			}			
		}
	}
	public void close(){
		_o = new BasicLocalSearchEntity[_to.size()];
		int i = -1;
		Iterator it = _to.iterator();
		while(it.hasNext()){
			BasicLocalSearchEntity e = (BasicLocalSearchEntity)it.next();
			i++;
			_o[i] = e;
			_o[i].setID(i);
		}

		for(int j = 0; j < _to.size(); j++){
			BasicLocalSearchEntity e = _o[j];
			//System.out.println("LocalSolver::close, build dependency graph for entity " + e.name());
			if(_map.get(e) == null)
				_map.put(e, new HashSet<BasicLocalSearchEntity>());
			if(_mapDependency.get(e) == null)
				_mapDependency.put(e, new HashSet<BasicLocalSearchEntity>());
		}

		for(int j = 0; j < _to.size(); j++){
			BasicLocalSearchEntity e = _o[j];
			BasicLocalSearchEntity[] de = e.getDependEntities();
			if(de != null){
				for(int jj = 0; jj < de.length; jj++){
					//HashSet<BasicLocalSearchEntity> S = _map.get(de[i]);
					//S.add(e);
					//System.out.println("LocalSolver::close, de[" + jj + "] = " + de[jj].name());
					_map.get(de[jj]).add(e);
					_mapDependency.get(e).add(de[jj]);
				}			
			}
		}
		initPropagate();
	}
	
	public void println(){
		System.out.println("LocalSolver::println, o = ");
		for(int i = 0; i < _o.length; i++){
			System.out.print(_o[i].name() + " defines: ");
			HashSet<BasicLocalSearchEntity> A = _map.get(_o[i]);
			Iterator it = A.iterator();
			while(it.hasNext()){
				BasicLocalSearchEntity e = (BasicLocalSearchEntity)it.next();
				System.out.print(e.name() + " ");
			}
			System.out.println("");
		}
		//System.out.println("_dependency is:");
		
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	
	}

}
